// https://leetcode-cn.com/problems/evaluate-division/
// 399. Evaluate Division
// You are given an array of variable pairs equations and an array of
// real numbers values, where equations[i] = [Ai, Bi] and
// values[i] represent the equation Ai / Bi = values[i]. Each
// Ai or Bi is a string that represents a single variable
// You are also given some queries, where queries[j] = [Cj, Dj]
// represents the jth query where you must find the answer for
// Cj / Dj = ?
// Return the answers to all queries. If a single answer cannot be
// determined, return -1.0

export class UnionFind {
    parent: number[];
    weight: number[];
    constructor(n: number) {
        this.parent = new Array(n);
        this.weight = new Array(n);
        for (let i = 0; i < n; i++) {
            this.parent[i] = i;
            this.weight[i] = 1;
        }
    }

    union(x: number, y: number, value: number) {
        const rootX = this.find(x);
        const rootY = this.find(y);

        if (rootX === rootY) return;
        this.parent[rootX] = rootY;
        this.weight[rootX] = (this.weight[y] * value) / this.weight[x];
    }

    find(x: number): number {
        if (x !== this.parent[x]) {
            const origin = this.parent[x];
            this.parent[x] = this.find(this.parent[x]);
            this.weight[x] *= this.weight[origin];
        }

        return this.parent[x];
    }

    isConnected(x: number, y: number): number {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX === rootY) {
            return this.weight[x] / this.weight[y];
        } else {
            return -1;
        }
    }
}

export function calcEquation(
    equations: string[][],
    values: number[],
    queries: string[][]
): number[] {
    const size = equations.length;
    const unionFind = new UnionFind(size * 2);
    const map: Map<string, number> = new Map();
    let id = 0;
    for (let i = 0; i < size; i++) {
        const [x, y] = equations[i];
        if (!map.has(x)) {
            map.set(x, id++);
        }
        if (!map.has(y)) {
            map.set(y, id++);
        }
        unionFind.union(map.get(x)!, map.get(y)!, values[i]);
    }

    const querySize = queries.length;
    const result: number[] = new Array(querySize);
    for (let i = 0; i < querySize; i++) {
        const [x, y] = queries[i];
        const a = map.get(x);
        const b = map.get(y);
        if (a === undefined || b === undefined) {
            result[i] = -1;
        } else {
            result[i] = unionFind.isConnected(a, b);
        }
    }
    return result;
}
